% <OKUNO>BNCH5.PL.2,  7-Jul-84 11:59:06, Edit by OKUNO

% [11] **** Tree traversing ****

/* Bigapp : A non-determinate computation involving structure
   accessing and lots of backtracking.  Written by Paul F. Wilk.
*/

:- public q111/1, conslist/2, concat/3, bigapp/1.
:- public q112/1.

/*
To optimize the compiled code, add the next declarations:

:- mode conslist(+,-), concat(-,-,+), bigapp(+).
:- mode q111(-), q112(-).
:- fastcode.
:- compactcode.
*/

conslist(0 ,[]).
conslist(N,[1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5|L]) :-
        N > 0,
        N1 is N - 25,
        conslist(N1,L).

concat([],L,L).
concat([X|L1],L2,[X|L3]) :- concat(L1,L2,L3).

bigapp(L) :- concat(L1,L2,L), fail.
bigapp(←).

/*
[11-1:] Measure the time of consing 1000 elements by 25 elements.
	do "q111(100)." for one hundred iterations.
*/

q111(N) :- 
     statistics(garbage←collection,[←,←|G1]),!,
     statistics(runtime,[←,←]),!,
     loop←q111(0,N),
     statistics(runtime,[←,T1]),!,
     statistics(garbage←collection,[←,←|G2]),!,
     statistics(runtime,[←,←]),!,
     loop←dummy(0,N),
     statistics(runtime,[←,T2]),
     statistics(garbage←collection,[←,←|G3]),!,
     G1 = [Gt1], G2 = [Gt2], G3 = [Gt3],
     G4 is Gt2 + Gt2 - Gt1 - Gt3,
     T3 is T1-T2-G4, Total is T1-T2,
     write('Total = '), write(Total),
     write('ms,  runtime = '), write(T3),
     write('ms,  gctime = '), write(G4),
     write('ms,   for '), write(N), write(' iterations.'), nl.

loop←q111(N,N) :- !.
loop←q111(I,N) :-
     I1 is I+1, conslist(1000,L), !, loop←q111(I1,N).

loop←dummy(N,N) :- !.
loop←dummy(I,N) :-
     I1 is I+1, !, loop←dummy(I1,N).

/*
[11-2:] Measure the time of decomposing a list of length 1000.
	do "q112(1)." for only once.
*/

q112(N) :- 
     conslist(1000,L), assert(list1000(L)), !,
     statistics(garbage←collection,[←,←|G1]),!,
     statistics(runtime,[←,←]),!,
     loop←q112(0,N),
     statistics(runtime,[←,T1]),!,
     statistics(garbage←collection,[←,←|G2]),!,
     statistics(runtime,[←,←]),!,
     loop←list1000(0,N),
     statistics(runtime,[←,T2]),
     statistics(garbage←collection,[←,←|G3]),!,
     G1 = [Gt1], G2 = [Gt2], G3 = [Gt3],
     G4 is Gt2 + Gt2 - Gt1 - Gt3,
     T3 is T1-T2-G4, Total is T1-T2,
     write('Total = '), write(Total),
     write('ms,  runtime = '), write(T3),
     write('ms,  gctime = '), write(G4),
     write('ms,   for '), write(N), write(' iterations.'), nl.

loop←q112(N,N) :- !.
loop←q112(I,N) :-
     I1 is I+1, list1000(L), !, bigapp(L), loop←q112(I1,N).

loop←list1000(N,N) :- !.
loop←list1000(I,N) :-
     I1 is I+1, list1000(L), !, loop←list1000(I1,N).